原始题目:剑指 Offer 33. 二叉搜索树的后序遍历序列 (opens new window)
解题思路:
后序遍历的定义:【左子树 | 右子树 | 根节点】
二叉搜索树定义:左子树中所有节点值 根节点的值;右子树中所有节点的值 根节点的值;其左右子树也为二叉搜索树。
根据以上两个定义,可以得到如下结论:
- 拿到序列最后一个元素的值 ,可以将序列分为左子树和右子树。其中,小于 x 的连续元素的集合为左子树的序列;大于 x 的连续元素的结合为右子树的序列。
- 左子树的序列和右子树的序列同样满足结论 。
根据以上的结论,可以使用一个指针 和 。 指向的元素会与 进行对比, 记录的是左子树的右边界(不包含 )。
验证函数
**参数传递:**后序遍历数组 ,数组的左右边界(包含)、。
终止条件: 大于等于 r 时,返回 。
递推工作:
- 指针指向 , 为 的值
- 循环检查:如果 指向的元素小于 ,说明该元素属于左子树, 自增。
- 用 记录 的值,此时 区间为左子树。
- 循环检查:如果 指向的元素大于 ,说明该元素属于右子树, 自增。
- 通过以上两个循环,对于合法的序列,此时应该有 ,然后分别对左子树区间 和右子树区间 进行下一层的递归,返回递归结果。
代码:
public boolean verifyPostorder(int[] postorder) {
if (postorder == null || postorder.length == 0) {
return true;
}
return verifyPostOrder(postorder, 0, postorder.length - 1);
}
private boolean verifyPostOrder(int[] postOrder, int l, int r) {
if (l >= r) {
return true;
}
int p = l;
while (postOrder[p] < postOrder[r]) {
p++;
}
// [l,m) 为左子树
int m = p;
while (postOrder[p] > postOrder[r]) {
p++;
}
// 如果是合法的后序遍历,那么此时 p == r
return p == r && verifyPostOrder(postOrder, l, m - 1) && verifyPostOrder(postOrder, m, r - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
复杂度分析
时间复杂度: 为序列的长度。验证函数每一层只会去掉一个根节点,因此递归占用 。最坏情况下,树退化成链表,每一层占用的时间为 。
空间复杂度: 为序列的长度。最差情况下,树退化成链表,递归深度达到 。